package com.dataStructure.backtrack;

import java.util.*;


public class LeetCode {

    /**
     * 用回溯法解决组合问题
     * 1. 理解树形结构
     * 2. 确定递归函数
     * 3. for () {
     *     //add
     *     //递归
     *     //回溯
     * }
     *
     * //  1. 基于给出的数组元素不会出现重复的情况
     *
     * ----- 如果组合问题遇到不可以重复选取时，则递归函数传递索引值就得加一
     *------ 否则组合遇到可以重复选取时，则递归函数传递索引值不变
     *
     *    2. 给出的数组元素会出现重复的情况
     *    比如 力扣40，这里涉及到一个数层去重和树枝去重，
     *    解决数层去重，首先对数组进行排序，然后我们初始化一个 bool used数组，如果 ar[i] == ar[i-1]并且
     *    used[i -1] == false,就表明这个元素是在一个数层里面；如果为 true表示已经在一个树枝上面使用过
     *
     *
     */

      LinkedList<Integer> sresult = new LinkedList<>();

     List<List<Integer>> result = new ArrayList<>();

     LinkedList<String> ssresult = new LinkedList<>();
     List<List<String>> strResult = new ArrayList<>();


    /**
     * 全排列||，元素可以重复
     * 力扣47
     */
    List<List<Integer>> result47 = new ArrayList<>();
    LinkedList<Integer> path47 = new LinkedList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];

        backTrack47(nums, visited);
        return result47;
    }

    void backTrack47(int[] nums, boolean[] visited) {
        if (path47.size() == nums.length) {
            result47.add(new LinkedList<>(path47));
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            if (visited[i]) {
                continue;
            }

            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }

            visited[i]  = true;
            path47.add(nums[i]);
            backTrack47(nums, visited);
            path47.removeLast();
            visited[i] = false;

        }

    }


    /**
     * 子集 2，给出条件出现重复元素

     */
    List<List<Integer>> result90 = new ArrayList<>();
    LinkedList<Integer> path90 = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTrack90(nums,  0);
        return result90;
    }

    void backTrack90(int[] nums, int index) {
        result90.add(new ArrayList<>(path90));
        if (index == nums.length) {
            return;
        }

        for (int i = index; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] ) {
                continue;
            }
            path90.add(nums[i]);
            backTrack90(nums, i + 1);
            path90.removeLast();
        }
    }

    /**
     * 78. 子集
     */
    List<List<Integer>> result78 = new ArrayList<>();
    LinkedList<Integer> path78 = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTrack78(nums, 0);
        return result78;
    }

    void backTrack78(int[] nums, int index) {
        result78.add(new ArrayList<>(path78));

        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            path78.add(nums[i]);
            backTrack78(nums, i + 1);
            path78.removeLast();
        }
    }

    /**
     *
     * 力扣 496
     */

    List<List<Integer>> result496 = new ArrayList<>();
    LinkedList<Integer> path496 = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
            boolean[] visited = new boolean[nums.length];
            backTrack496(nums, visited);
            return result496;

    }

    void backTrack496(int[] nums, boolean[] visited) {
        if (path496.size() == nums.length) {
            result496.add(new ArrayList<>(path496));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            path496.add(nums[i]);
            backTrack496(nums, visited);
            path496.removeLast();
            visited[i] = false;

        }
    }




    /**
     * 组合总和  力扣40 回溯
     *
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used = new boolean[candidates.length];
        Arrays.sort(candidates);
        backTrack40(candidates,target,0,0,used);

        return result;
    }

    public void backTrack40(int[] candidates,int target,int index,int sum,boolean[] used) {
        if (sum == target) {
            if (result.contains(new ArrayList<>(sresult)))
            result.add(new ArrayList<>(sresult));
            return;
        }

        for (int i = index; i < candidates.length ;i++) {
            if (i > 0 && candidates[i] == candidates[i -1] && used[i -1] == false) {
                continue;
            }
            sresult.add(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backTrack40(candidates,target,i + 1,sum, used);
            used[i] = false;
            sum -= candidates[i];
            sresult.removeLast();
        }
    }





    /**
     * 组合总和 力扣39
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTrack39(candidates,target,0,0);
        return result;
    }


    public void backTrack39(int[] candidates,int target,int index,int sum) {
        if (sum == target) {
            result.add(new ArrayList<>(sresult));
            return;
        }
        if (sum > target) {
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            sresult.add(candidates[i]);
            sum += candidates[i];
            backTrack39(candidates,target,i,sum);
            sum -= candidates[i];
            sresult.removeLast();
        }
    }




    /**
     * 电话号码的字母组合 力扣17

     */
    StringBuilder path = new StringBuilder();
    List<String> result1 = new ArrayList<>();
    String[] ar = {"","","abc","def","ghi","jkl","mno"
            ,"pqs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) {
            return result1;
        }

        backTrack(digits,0);
        return result1;
    }

    public void backTrack(String digits,int index) {
        if (path.length() == digits.length()) {
            StringBuilder builder = new StringBuilder(path);
            result1.add(builder.toString());
        }

        char c = digits.charAt(index);
        int num =  c - '0';
        String str = ar[num];
        for (int i = 0;i < str.length();i++) {
            path.append(str.charAt(i));
            backTrack(digits,index + 1);
            path.deleteCharAt(i);
        }


    }



    /**
     * 力扣77  组合问题
     */

    public List<List<Integer>> combine(int n, int k) {
        backTrace77(1,n,k);
        return result;
    }
    public  void backTrace77(int startIndex,int n,int k) {
        if(sresult.size() == k) {
            result.add(new ArrayList<>(sresult));
            System.out.println(startIndex);
            return;
        }

        for (int i = startIndex; i <= n; i++) {
            sresult.add(i);
            backTrace77(i + 1,n,k);
            System.out.println(i);
            sresult.removeLast();
        }
    }
}
